package com.yx.study.leet.questionList.questions;

import org.junit.Test;

import java.util.*;

/**
 * 39. 组合总和
 * https://leetcode.cn/problems/combination-sum/
 */
public class Solution39 {
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        Map<Integer,Integer> map = new HashMap<>();
//        List<List<Integer>> lists = new ArrayList<>();
//        for (int i = 0; i < candidates.length; i++) {
//            map.put(candidates[i],candidates[i]);
//        }
//        for (int i = 0; i < candidates.length; i++) {
//            int remaidn = target % candidates[i];
//            int divid = target / candidates[i];
//            if (remaidn==0&&divid==1){
//               lists.add(Arrays.asList(candidates[i]));
//            }else if (remaidn==0&&divid!=1){
//                lists.add(getList(divid,candidates[i]));
//            }
//            if (map.get(remaidn)!=null){
//             // 存在余数 符合组合要求
//                List<Integer> list = getList(divid, candidates[i]);
//                list.add(remaidn);
//                lists.add(list);
//            }
//        }
//        return lists;
//    }
//
//    private List<Integer> getList(int divid,int num){
//        List<Integer> list  = new ArrayList<>();
//        for (int i = 0; i < divid; i++) {
//            list.add(num);
//        }
//        return list;
//    }

    /**
     * 官方题解
     * */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }

    }

    @Test
    public void test() {
        // [2,3,6,7]
        //7
        int[] nums = {2, 3, 6, 7};
        System.out.println(combinationSum(nums, 7));
    }
}
